package zuosheng.dongtaiguihua;

/**
 * @author lj
 * @Description: 问题：给你一个数组 arr，和一个整数 aim。如果可以任意选择 arr 中的数字，能不能累加得到 aim，返回 true 或者 false。
 * @date 2020-11-13 15:14
 * @QQ 851477108
 */


public class Code_08_Money_Problem {
    public static void main(String[] args) {
        int[] arr = {2, 3, 5};
        int aim = 7;
        System.out.println(money1(arr,aim));
        System.out.println(money2(arr,aim));
    }

    public static boolean money1(int[] arr, int aim){
        return process1(arr, 0, 0, aim);
    }

    public static boolean process1(int[] arr, int i, int sum, int aim){
        if (sum == aim){
            return true;
        }
        if (i == arr.length){
            return false;
        }

        boolean flag1 = process1(arr,i+1,sum,aim);
        boolean flag2 = process1(arr,i+1,sum+arr[i],aim);
        return flag1||flag2;
    }

    public static boolean money2(int[] arr, int aim){
        if (arr == null || arr.length < 1){
            return false;
        }
        // 构建状态表：要注意在原数组长度基础上加1
        // 可变参数：i 和 sum  只需要关心 aim 之前的累加和就好了
        boolean[][] dp = new boolean[arr.length+1][aim+1];
        // baseCase：填好dp的最后一行，上面每一行的dp值都依赖下面一行的dp值得出
        for(int i = arr.length, sum = 0; sum <= aim; sum++) {
            if (sum == aim) {
                dp[i][sum] = true;    // 目标值处设置为 true
            } else {
                dp[i][sum] = false;
            }
        }
        // 其他位置的 dp 值：依赖下一行位置的两个位置处的 dp 值
        for (int i = arr.length - 1; i >= 0; i--){
            for (int sum = aim - 1; sum >= 0; sum--){
                if (sum + arr[i] > aim){
                    // 填充最后一列的 dp 值,其实一个为 true，正上方的位置都为 true
                    dp[i][sum] = dp[i+1][sum];
                }else {
                    // dp[i][sum]为true有两种情况：dp[i+1][sum]为true或者dp[i+1][sum+arr[i]]为ture
                    dp[i][sum] = dp[i+1][sum] || dp[i+1][sum+arr[i]];
                }
            }
        }
        return dp[0][0];
    }

}
